﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include"Queue.h"
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	struct BinTreeNode* left; // 指向当前结点左孩⼦
	struct BinTreeNode* right; // 指向当前结点右孩⼦
	BTDataType val; // 当前结点值域
}BTNode;

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode =(BTNode*) malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->right = NULL;
	newnode->left = NULL;
}

//创建二叉树
BTNode*  CreatTree()
{
	BTNode* n1 = BuyBTNode(1);
	BTNode* n2 = BuyBTNode(2);
	BTNode* n3 = BuyBTNode(3);
	BTNode* n4 = BuyBTNode(4);
	BTNode* n5 = BuyBTNode(5);
	BTNode* n6 = BuyBTNode(6);
	BTNode* n7 = BuyBTNode(7);
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	 
	return n1;
}

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ",root->val );
	PreOrder(root->left ); 
	PreOrder(root->right);
}


//中序遍历
//左 根 右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);

	printf("%d ", root->val);

	InOrder(root->right);

}


// 二叉树后序遍历
//左 右 根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left );
	PostOrder(root->right );
	printf("%d ", root->val);

}


//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->val );

		if (front->left)
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);
	}

	QueueDestroy(&q);
}


//1、二叉树节点个数
//要求二叉树结点个数，即当下结点+左子树+右子树
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

//通过判断不为空就++size，取访问所有节点，遇到空节点就直接返回
//缺点：需要重置 size” 的本质原因
int size;

void TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return ;
	}

	size++;
	TreeSize(root->left );
	TreeSize(root->right);

}


//2、二叉树叶子节点个数
//求左右子树叶子结点的和
//结束条件是节点为空，或者左右子树为空
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);

}

//3、二叉树第k层节点个数
//求k-1层左右子树节点之和
//当k==1时说明已经递推到第k层了
//以及在递推过程中遇到空节点，返回0即可
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);

}


//4、⼆叉树的深度/⾼度
//左右子树中更深的那个深度 + 1
int BinaryTreeDepth(BTNode* root)
{
	if (NULL == root)
	{
		return 0;
	}
	int LeftHight = BinaryTreeDepth(root->left ) ;
	int RightHight = BinaryTreeDepth(root->right) ;

	return LeftHight > RightHight ? LeftHight + 1 : RightHight + 1;


}


// 5、二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->val == x)
	{
		return root;
	}

	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}


	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}

	return NULL;
	
}


 

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(char* a, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->val = a[*pi];
	(*pi)++;
	root->left = BinaryTreeCreate(a,pi);
	root->right = BinaryTreeCreate(a, pi);

	return root;
}


// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));

	free(*root);
	*root = NULL;
}



//判断二叉树是否为完全二叉树
//---队列
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);


	//找队列第一个空
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//判断是不是空节点，不是的话就继续入左右子树的节点
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	//剩下的都是空的话就代表是完全二叉树
	//否则就不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//有一个不为空就代表不是完全二叉树
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}


int main()
{
	char a[] = { "ABD##E#H##CF##G##" };
	int i = 0;
	BTNode* root = BinaryTreeCreate(a,&i);
	PreOrder(root);
	BinaryTreeDestory(&root);
	return 0;

}

////前序遍历 根结点、左⼦树、右⼦树
////void PreOrder(BTNode* root)
////{
////	if (root == NULL)
////	{
////		printf("NULL ");
////		return;
////	}
////	printf("%d ",root->val );
////	PreOrder(root->left );
////	PreOrder(root->right);
////
////
////}
////
////中序遍历 左⼦树、根结点、右⼦树
////void InOrder(BTNode* root)
////{
////	if (root == NULL)
////	{
////		printf("NULL ");
////		return;
////	}
////	InOrder(root->left );
////	printf("%d ", root->val);
////	InOrder(root->right );
////
////
////}
////
////后序遍历 左⼦树、右⼦树、根结点
////void PostOrder(BTNode* root)
////{
////	if (root == NULL)
////	{
////		printf("NULL ");
////		return;
////	}
////	PostOrder(root->left );
////	PostOrder(root->right);
////	printf("%d ", root->val);
////
////}
////
////int size;
////
////求数的节点个数
////void TreeSize(BTNode* root)
////{
////	if (root == NULL)
////	{
////		return ;
////	}
////
////	size++;
////	TreeSize(root->left );
////	TreeSize(root->right);
////
////}
////
////void TreeSize(BTNode* root,int *size)
////{
////	if (root == NULL)
////	{
////		return ;
////	}
////
////	(*size)++;
////	TreeSize(root->left,size );
////	TreeSize(root->right,size);
////
////}
////
////int  TreeSize(BTNode* root)
////{
////
////	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
////	左子树加右子树在加自己 -- 指挥打工人
////
////}
////
////
////int TreeHeight(BTNode* root)
////{
////	if (root == NULL)
////		return 0;
////
////	return TreeHeight(root->left) > TreeHeight(root->right)
////		? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
////}
////
//// 
////
////左高度和右高度大的加1
////int TreeHeight(BTNode* root)
////{
////	if (root == NULL)
////	{
////		return 0;
////	}
////	int leftHeight  = TreeHeight(root->left);
////	int rightHeight = TreeHeight(root->right);
////
////	return  leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
////}
////
////int main()
////{
////	BTNode* root = CreatTree();
////	PostOrder(root);
////	int size = BinaryTreeLeafSize(root);
////	printf("%d", size);
////	int size = BinaryTreeDepth(root);
////	printf("%d", size);
////
////	return 0;
////
////}
////
////
//////求第k层的宽度 当前树左子树的第k-1层+当前树右子树的第k-1层
////int TreeKLevel(BTNode* root, int k)
////{
////	assert(k > 0);
////
////	if (root == NULL)
////		return 0;
////
////	if (k == 1)
////		return 1;
////
////	return TreeKLevel(root->left, k - 1)
////		+ TreeKLevel(root->right, k - 1);
////}
////
//////判断是不是完全二叉树
////bool TreeComplete(BTNode* root)
////{
////	Queue pq;
////	QueueInit(&pq);
////
////	if (root)
////	{
////		QueuePush(&pq,root);
////	}
////
////	while (!QueueEmpty(&pq))
////	{
////		QDataType front = QueueFront(&pq);//取队头树的节点
////		QueuePop(&pq);
////
////		if (front == NULL)//如果碰到第一个空了，就跳出去，判断队列里面剩下的节点是不是都为空
////		{
////			break;   
////		}
////		else
////		{
////			QueuePush(&pq, front->left );
////			QueuePush(&pq, front->right );
////
////		}
//	}
//
//	while (!QueueEmpty(&pq))
//	{
//		QDataType front = QueueFront(&pq);//取队头树的节点
//		QueuePop(&pq);
//
//		if (front!= NULL)
//		{
//			QueueDestroy(&pq);
//			return false;
//		}
//
//	}
//
//	//销毁队列
//	QueueDestroy(&pq);
//	return true;
//}
//
////层序遍历
//void LevelOrder(BTNode* root)
//{
//	Queue q;
//	QueueInit(&q);
//	if (root)
//		QueuePush(&q, root);
//
//	while (!QueueEmpty(&q))
//	{
//		BTNode* front = QueueFront(&q);
//		QueuePop(&q);
//		printf("%d ", front->val );
//
//		if (front->left)
//			QueuePush(&q, front->left);
//
//		if (front->right)
//			QueuePush(&q, front->right);
//	}
//
//	QueueDestroy(&q);
//}
//
////销毁
//void BinaryTreeDestory(BTNode** root)
//{
//	if (*root == NULL)
//		return;
//	BinaryTreeDestory(&(*root)->left );
//	BinaryTreeDestory(&(*root)->right);
//
//	free(*root);
//	*root = NULL;
//
//}
//
//////查找
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
//	if (root == NULL)
//		return NULL;
//	if (root->val == x)
//		return root;
//	BTNode* left = BinaryTreeFind(root->left , x);
//	if (left)
//		return left;
//	BTNode* right = BinaryTreeFind(root->right, x);
//	if (right)
//		return right;
//
//	return NULL;
//}
//
////查找
////BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
////{
////	if (root == NULL)
////		return NULL;
////	if (root->val == x)
////		return root;
////	BTNode* left = BinaryTreeFind(root->left , x);
////	if (left)
////		return left;
////	return BinaryTreeFind(root->right, x);
//// 
////}
//
//int main()
//{
//	//BTNode* tree = CreatTree();
//	//InOrder(tree);
//	//PostOrder(tree);
//
//	//size = 0;
//
//	//int size = 0;
//	//TreeSize(tree );
//	//printf("%d\n", TreeSize(tree) );
//
//	//size = 0;
//	//TreeSize(tree );
//	//printf("%d", size);
//	//printf("%d\n", TreeHeight(tree));
//	//printf("%d", TreeHeight(tree));
//	//printf("%d",TreeKLevel(tree, 3));
//
//	
//	//LevelOrder(tree);
//
//	//bool ret = TreeComplete(tree);
//	//if (ret == 0)
//	//{
//	//	printf("不是完全二叉树");
//	//}
//	//else
//	//{
//	//	printf("是完全二叉树");
//	//}
//
//	BTNode* tree = CreatTree();
//	//printf("TreeFind:%p\n", BinaryTreeFind(tree, 5));
//	//printf("TreeFind:%p\n", BinaryTreeFind(tree, 50));
//
//	BinaryTreeDestory(tree);
//	return 0;
//
//}

//树节点的结构
//typedef int BTDataType;
//
//typedef struct BinaryTreeNode
//{
//	struct BinTreeNode* left; // 指向当前结点左孩⼦
//	struct BinTreeNode* right; // 指向当前结点右孩⼦
//	BTDataType val; // 当前结点值域
//}BTNode;
//
////树节点申请
//BTNode* BuyBTNode(BTDataType x)
//{
//	BTNode* newnode =(BTNode*) malloc(sizeof(BTNode));
//	if (newnode == NULL)
//	{
//		perror("malloc");
//		exit(-1);
//	}
//	newnode->val = x;
//	newnode->right = NULL;
//	newnode->left = NULL;
//
//	return newnode;
//}
//
////创建二叉树
//BTNode*  CreatTree()
//{
//	BTNode* n1 = BuyBTNode(1);
//	BTNode* n2 = BuyBTNode(2);
//	BTNode* n3 = BuyBTNode(3);
//	BTNode* n4 = BuyBTNode(4);
//	BTNode* n5 = BuyBTNode(5);
//	BTNode* n6 = BuyBTNode(6);
//	BTNode* n7 = BuyBTNode(7);
//	n1->left = n2;
//	n1->right = n4;
//	n2->left = n3;
//	n3->left = n7;
//	n4->left = n5;
//	n4->right = n6;
//	 
//	return n1;
//}